package com.ztom.v2;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZhangTao
 */
public class Code46FlattenBinaryTreeToLinkedList {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public void flatten1(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序遍历, 使用 prev 记录上一个节点
        Deque<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        TreeNode pre = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            if (pre != null) {
                pre.left = null;
                pre.right = node;
            }
            if (node.right != null) {
                stack.addLast(node.right);
            }
            if (node.left != null) {
                stack.addLast(node.left);
            }
            pre = node;
        }
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        // 先序: 头左右
        // 找前继节点: 当前节点的右子树挂在左子树的最右节点
        TreeNode cur = root;
        TreeNode preNode = null;
        while (cur != null) {
            // 考察存在左子树
            if (cur.left != null) {
                // 当前节点左子树
                TreeNode curL = cur.left;
                // 左子树最右节点
                preNode = cur.left;
                while (preNode.right != null) {
                    preNode = preNode.right;
                }

                // 当前节点右子树挂前继节点上
                preNode.right = cur.right;

                // 当前节点左子树挂右指针上
                cur.left = null;
                cur.right = curL;
            }
            // 上面操作完就没左子树了, 直接去右子树
            cur = cur.right;
        }
    }
}
